1. Field of the Invention
The present invention relates to an apparatus and method for storing in a computer readable medium keyframes of a video image or excerpts from a document, and more particularly to providing for storage thereof so as to optimize retrieval from a relatively slow memory device.
2. Description of the Related Art
In a video indexing process, keyframes that visually describe a video image may be extracted from the video by cut detection and keyframe filtering such as described in pending patent applications "Significant Scene Detection and Frame Filtering for a Visual Indexing System", U.S. Ser. No. 08/867,140 pending and "Video Indexing System", U.S. Ser. No. 08/867,145 pending, having amongst their inventors the inventors of the present invention, to create an index. In video cut detection and keyframe filtering, keyframes are selected from a large number of possible frames (30 frames per second of video, typically). Even after the keyframe filtering process, the number of keyframes is considerable, approximately 250 keyframes per video tape. Typically then, the size of an index is approximately 1 MB, if the keyframes are scaled down to 160.times.120 resolution and compressed into JPEG format. Without scaling and compression, the size of the index could be 50 MB or more. At this size, retrieval of keyframes could take considerable amount of time, especially if the retrieval is performed over slow channels such as high latency networks (e.g., Internet, Intranet, etc.) or linear tape mediums such as VHS tape.
Similarly, for web sites, web pages or multimedia or hypermedia documents including blobs are presented. A multimedia document or web page containing video (or images) can require a large amount of memory which may be on the order of tens of megabytes. Time required to download such a multimedia document or software may be considerable with a typical 28.8 kb/sec modem.
A website may include a large number of possible web pages, multimedia documents and links which may be unwieldy for a user to navigate. Each multimedia document or web page may include blobs. The blobs may include audio, video, text, hypertext links or links to other documents. A website retrieval of pages or multimedia documents and their respective blobs, especially those a user has an interest in, may take a considerable amount of time as blobs typically are stored in temporal or static hierarchies. A multimedia document may be created which provides a user with web pages having audio, video, text and links based on user preferences or other prespecified criteria.
To optimize retrieval of the keyframes or blobs in a user friendly manner, an index or multimedia document is created using a hierarchical structure representation. Temporal hierarchies have been described in the literature, such as Ueda, Hirotada and Takafumi Miyatake. "Automatic Scene Separation and Tree Structure GUI for Video Editing", The Fourth ACM International Multimedia Conference, Multimedia (Nov. 18-22, 1996): 405-406, as a conceptual representation of keyframes. The present invention creates a linear index structure or linear multimedia document structure out of the temporal hierarchy, allowing for optimized retrieval. Currently, storage in databases is typically not optimized for retrieval, but instead, optimized for transaction processing. For example, database systems are optimized for transaction processing such as editing data (i.e., inserting, updating and deleting data) in a database of the system. Query optimization is available also; however, benchmarks of database systems concentrate on changing data as fast as possible with parallel requests.
In databases, order of retrieval is not known in advance since database management systems typically have no knowledge of stored data content or what query will be requested.
In a Digital Compact Cassette (DCC) format, an index system describes which tracks are on a specific tape; however, priority between different tracks does not exist; therefore, optimization of retrieval of the content is not possible.
For a Web page or another similar type multimedia document, information is provided to a user based on a format prespecified by the provider, not on a user-stored preference.